﻿//1.完全背包
//https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

#include <iostream>
#include <vector>
using namespace std;
 int main() 
 {
     int n,V;
     cin >> n >> V;
     vector<int> v(n + 1),w(n + 1);
     for(int i = 1;i <= n;i++)
         cin >> v[i] >> w[i];
     //dp[i][j] = 考虑前i种物品，背包容量为j时能获得的最大价值
     //状态转移方程：
     //dp[i][j] = max(不选第i种物品, 选第i种物品) = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
     vector<vector<int>> dp(n + 1,vector<int>(V + 1));
     for(int i = 1;i <= n;i++)
         for(int j = 0;j <= V;j++)
         {
             // 不选第i种物品
             dp[i][j] = dp[i - 1][j];
             if(j >= v[i])
                  // 选第i种物品，注意这里是dp[i][j-v[i]]而不是dp[i-1][j-v[i]]
                  // 因为完全背包中每种物品可以选多次
                 dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i]);
         }
     cout << dp[n][V] << endl;

     //dp[i][j]表示：考虑前i种物品，背包容量恰好为j时能获得的最大价值
     //用-1表示该状态无法达到（无法恰好装满）
     dp.assign(n + 1,vector<int>(V + 1));
     //dp[0][0] = 0   (容量0的背包自然装满，价值0)
     //dp[0][j] = -1 (j > 0，没有物品时无法装满任何正容量背包)
     for(int i = 1;i <= V;i++) dp[0][i] = -1;
     //状态转移方程：
     //如果 dp[i][j-v[i]] != -1:
     //    dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
     //否则:
     //dp[i][j] = dp[i-1][j]  (可能为-1)
      for(int i = 1;i <= n;i++)
         for(int j = 0;j <= V;j++)
         {
             // 不选第i种物品
             dp[i][j] = dp[i - 1][j];
             // 只有当前容量减去物品体积后能恰好装满，才能转移
             if(j >= v[i] && dp[i][j - v[i]] != -1)
                 dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i]);
         }
     cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
     return 0;
 }

//空间优化
int main()
{
    int n, V;
    cin >> n >> V;
    vector<int> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    vector<int> dp(V + 1);
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;

    dp.assign(V + 1, 0);
    for (int i = 1; i <= V; i++) dp[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
        {
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

//2.零钱兑换
//https://leetcode.cn/problems/coin-change/description/
//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
//计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 - 1 。
//你可以认为每种硬币的数量是无限的。
//示例 1：
//输入：coins = [1, 2, 5], amount = 11
//输出：3
//解释：11 = 5 + 5 + 1
//示例 2：
//输入：coins = [2], amount = 3
//输出： - 1
//示例 3：
//输入：coins = [1], amount = 0
//输出：0
//提示：
//1 <= coins.length <= 12
//1 <= coins[i] <= 231 - 1
//0 <= amount <= 104

//dp[i][j]表示:使用前 i 种硬币凑出金额 j 所需的最少硬币数量。
//对于每个金额 j 和每种硬币 coins[i-1]：
//不选当前硬币：dp[i][j] = dp[i - 1][j]
//选当前硬币：dp[i][j] = dp[i][j - coins[i - 1]] + 1
//取两者中的较小值。
//即dp[i][j] = min(dp[i - 1][j],dp[i][j - coins[i - 1]] + 1)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int n = coins.size();
        // 定义一个很大的数，表示不可达
        const int INF = 0x3f3f3f3f;
        //dp[i][0] = 0：金额为0时不需要任何硬币（默认初始化为0）
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        //dp[0][j] = INF：没有硬币可用时，无法凑出任何正数金额
        for (int j = 1; j <= amount; j++) dp[0][j] = INF;
        // 遍历硬币种类
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= amount; j++)
            {
                // 初始化为不使用当前硬币的情况
                dp[i][j] = dp[i - 1][j];
                // 如果当前金额大于等于当前硬币面值，考虑使用当前硬币
                if (j >= coins[i - 1])
                    // 比较不使用当前硬币 vs 使用当前硬币
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        // 如果最终结果仍为INF，说明无法凑出目标金额
        return dp[n][amount] >= INF ? -1 : dp[n][amount];
    }
};



//3.零钱兑换II
//https://leetcode.cn/problems/coin-change-ii/description/
//给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
//请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
//假设每一种面额的硬币有无限个。
//题目数据保证结果符合 32 位带符号整数。
//示例 1：
//输入：amount = 5, coins = [1, 2, 5]
//输出：4
//解释：有四种方式可以凑成总金额：
//5 = 5
//5 = 2 + 2 + 1
//5 = 2 + 1 + 1 + 1
//5 = 1 + 1 + 1 + 1 + 1
//示例 2：
//输入：amount = 3, coins = [2]
//输出：0
//解释：只用面额 2 的硬币不能凑成总金额 3 。
//示例 3：
//输入：amount = 10, coins = [10]
//输出：1
//提示：
//1 <= coins.length <= 300
//1 <= coins[i] <= 5000
//coins 中的所有值 互不相同
//0 <= amount <= 5000

//定义 dp[j] 表示凑成金额 j 的组合数
//对于每种硬币，我们考虑使用它来更新所有可能达到的金额
//对于每个硬币 coin，对于每个金额 j >= coin：
//dp[j] += dp[j - coin[i]]
//dp[j]：不使用当前硬币时凑成金额 j 的组合数
//dp[j - coin]：使用至少一个当前硬币时凑成金额 j 的组合数
//由于是组合问题（顺序不重要），我们需要先遍历硬币，再遍历金额

class Solution {
public:
    int change(int amount, vector<int>& coins)
    {
        // 使用double避免整数溢出
        vector<double> dp(amount + 1);
        // 基础情况：凑成0元只有1种方式（不选任何硬币）
        dp[0] = 1;
        // 关键：先遍历硬币，保证组合数而不是排列数
        for (auto& x : coins)
            // 从当前硬币面额开始，避免负数索引
            for (int j = x; j <= amount; j++)
                // 状态转移：当前组合数 = 不使用该硬币的组合数 + 使用该硬币的组合数
                dp[j] += dp[j - x];
        return dp[amount];
    }
};




//4.完全平方数
//https://leetcode.cn/problems/perfect-squares/description/
//给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
//完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
//示例 1：
//输入：n = 12
//输出：3
//解释：12 = 4 + 4 + 4
//示例 2：
//输入：n = 13
//输出：2
//解释：13 = 4 + 9
//提示：
//1 <= n <= 104

//dp[i][j]表示：从前i个完全平方数选，其完全平方数的和等于j的所有选法中，所需最少的完全平方数个数
//对于每个状态 dp[i][j]，有两种选择：
//不使用当前平方数 i²：dp[i][j] = dp[i - 1][j]
//使用当前平方数 i²：dp[i][j] = dp[i][j - i²] + 1(注意这里还是dp[i]而不是dp[i - 1],因为i * i可以重复使用）
//
class Solution {
public:
    int numSquares(int n)
    {
        int m = sqrt(n);
        // dp[i][j]：使用前i个完全平方数（1^2, 2^2, ..., i^2）组成和为j的最少数量
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // 初始化：使用0个平方数时，只有和为0是可能的(需要0个平方数)(不可达)

        dp[0][0] = 0;
        //dp[0][j] = ∞（j > 0）：0个平方数无法组成任何正数
        for (int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                // 不使用第i个平方数（i^2）
                dp[i][j] = dp[i - 1][j];
                // 如果可以使用第i个平方数（i^2）
                if (j >= i * i)
                    dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        return dp[m][n];
    }
};


//使用一维数组进行空间优化
class Solution {
public:
    int numSquares(int n)
    {
        int m = sqrt(n);
        vector<int> dp(n + 1, 0x3f3f3f3f);
        dp[0] = 0;
        for (int i = 1; i <= m; i++)
            for (int j = i * i; j <= n; j++)
                dp[j] = min(dp[j], dp[j - i * i] + 1);
        return dp[n];
    }
};